package com.breeze.leetcode.hard;

import java.util.*;

/**
 * @url <a href="https://leetcode.cn/problems/cat-and-mouse-ii">1728. 猫和老鼠 II</a>
 * @author yangzh
 * @date 2025/2/11
 */
public class T1728CatAndMouseII {
    public static void main(String[] args) {
        // {"C...#","...#F","....#","M...."}
        // {"####F","#C...","M...."}
        String[] grid = {"C...#","...#F",".....","M...."};
        int catJump = 1, mouseJump = 2;

        T1728CatAndMouseII solution = new T1728CatAndMouseII();
        System.out.println(solution.canMouseWin(grid, catJump, mouseJump));
    }

    List<Position> visited = new ArrayList<>();
    Queue<Position> queue = new LinkedList<>();
    Map<Position, Position> predecessors = new HashMap<>();
    int row, col;

    /**
     * 只需要判断老鼠是否能在1000步以内抵达食物
     * 如果猫跟老鼠处在相同的位置，那么猫获胜。
     * 如果猫先到达食物，那么猫获胜。
     * 如果老鼠先到达食物，那么老鼠获胜。
     * 如果老鼠不能在 1000 次操作以内到达食物，那么猫获胜。
     * @param grid
     * @param catJump
     * @param mouseJump
     * @return
     */
    public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
        char[][] charGrid = new char[grid.length][grid[0].length()];
        Position mousePos = null, foodPos = null, catPos = null;
        col = grid[0].length();
        row = grid.length;
        for (int i = 0; i < grid.length; i++) {
            charGrid[i] = grid[i].toCharArray();
            for (int j = 0; j < charGrid[i].length; j++) {
                if (charGrid[i][j] == 'M') {
                    mousePos = new Position(i, j);
                } else if (charGrid[i][j] == 'C') {
                    catPos = new Position(i, j);
                } else if (charGrid[i][j] == 'F') {
                    foodPos = new Position(i, j);
                }
            }
        }

        // 如果食物不可达，猫胜利
        if (unreachableFood(charGrid, mousePos, foodPos)) {
            return false;
        }

        // 如果老鼠1000次以内先到食物，老鼠胜利，否则猫胜利
        for (int step = 0; step < 1000; step++) {
            // 如果老鼠找到食物，老鼠胜利


            // 如果猫找到老鼠，猫胜利

            // 如果猫找到食物，猫胜利
        }

        return true;
    }

    /**
     * 判断食物是否不可以抵达
     */
    private boolean unreachableFood(char[][] charGrid, Position mousePos, Position foodPos) {
        visited.add(mousePos);
        queue.add(mousePos);

        while (!queue.isEmpty()) {
            Position pos = queue.poll();

            if (pos.equals(foodPos)) {
                return false;
            }

            // 向上
            Position up = new Position(pos.x - 1, pos.y);
            if (pos.x > 0 && charGrid[pos.x - 1][pos.y] != '#' && !visited.contains(up)) {
                visited.add(up);
                queue.add(up);
                predecessors.put(up, pos);
            }

            // 向右
            Position right = new Position(pos.x, pos.y + 1);
            if (pos.y < col - 1 && charGrid[pos.x][pos.y + 1] != '#' && !visited.contains(right)) {
                visited.add(right);
                queue.add(right);
                predecessors.put(right, pos);
            }

            // 向下
            Position down = new Position(pos.x + 1, pos.y);
            if (pos.x < row - 1 && charGrid[pos.x + 1][pos.y] != '#' && !visited.contains(down)) {
                visited.add(down);
                queue.add(down);
                predecessors.put(down, pos);
            }

            // 向左
            Position left = new Position(pos.x, pos.y - 1);
            if (pos.y > 0 && charGrid[pos.x][pos.y - 1] != '#' && !visited.contains(left)) {
                visited.add(left);
                queue.add(left);
                predecessors.put(left, pos);
            }
        }

        return true;
    }

    static class Position {
        int x, y;

        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object object) {
            if (object instanceof Position pos) {
                return pos.x == x && pos.y == y;
            }
            return false;
        }
    }
}
